一.二分图的基本知识
1.二分图的概念
二分图又称作二部图，是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集,则称图G为一个二分图。我们一般把其中一部分称为x部，另一部分称为y部。
2.二分图的判定
1.在图中找一个点为起点 ，将它的邻接点标号为2，再将标号为2的点的邻接点标号为3，以此类推。注意，如果该点已经标号，则不进行操作。 
- 显然，标号为奇数的点和编号为偶数的点各在x部，y部，我们把它放在一起。如图：
3.我们判断每一条边，如果所有边其中一端在x部，另一端在y部，那么它就是一个二分图。显然，上图不是一个二分图。
3.二分图的性质
若无向图G为二分图，则G至少有两个顶点，且其所有回路的长度均为偶数。
4.二分图匹配与最大匹配
给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。如图，图中黄色线段是该图的一个匹配
在所有二分图匹配中，边数最多的匹配称为二分图的最大匹配，如图：
另外，
- 如果一个匹配中，图中的每个顶点都和匹配中某条边相关联，则称此匹配为完美匹配。
- 如果一个最大匹配M覆盖了X部或者Y部中的所有点，则成为完备匹配。如果覆盖了X部的所有点，则称X部到Y部的完备匹配，而如果覆盖了Y部的所有点，则称Y部到X部的完备匹配。而如果同时覆盖了X部和Y部的所有点，则它就是完美匹配。
- 由上述两条定义，我们可以得到：完备匹配包含了完美匹配
5.增广路径
M是图G的一个匹配，若P是图G中一条连通两个未匹配顶点的路径，并且属于M的边和不属于M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广路径。如图：(黄色为已匹配线段，蓝色为未匹配线段，高亮部分便是一条增广路径)
由增广路的定义可以推出下述结论：
- 因为第一条边和最后一条边都不属于M，所以P的路径长度必定为奇数。
- 不断寻找增广路可以得到一个更大的匹配M’，直到找不到更多的增广路。
- M为G的最大匹配当且仅当不存在M的增广路径。
那么，如何找一条增广路径呢？我们可以用dfs实现
二.二分图的最大匹配问题
1.匈牙利算法
匈牙利算法，由匈牙利数学家Edmonds于1965年提出。
算法的思路：如果该图有一条增广路径，那么我们进行取反操作（将匹配的变为未匹配的，将未匹配的变为匹配的），就可以得到更大的一组匹配。重复该操作，直至找不到增广路径，便得到了最大匹配。
找增广路径的算法前面已经讲过，只需从每一个顶点出发寻找增广路即可。如果找到了，就将最大匹配数加一。
代码如下（邻接表）：
//fx[],fy[]分别代表x部匹配的y部顶点，y部匹配的x部顶点
bool Augmented_path( int u ) {
for( int i = 0 ; i < Graph[ u ].size( ) ; i ++ ) {
int v = Graph[ u ][ i ];
if( !vis[ v ] ) {//如果该点未遍历
vis[ v ] = 1;
if( fy[ v ] == -1 || Augmented_path( fy[ v ] ) ) {//如果该点未匹配或以该点为起点有增广路径则找到了一条增广路径
fx[ u ] = v , fy[ v ] = u;//两点互相匹配
return 1;
}
}
}
return 0;//找不到增广路径
}
int Hungary( ) {
int Ans = 0;
memset( fx , -1 , sizeof( fx ) );
memset( fy , -1 , sizeof( fy ) );
for( int i = 1 ; i <= n ; i ++ ) {
if( fx[ i ] == -1 ) {//如果该点未匹配，则以它为起点找增广路径
memset( vis , 0 , sizeof( vis ) );
Ans += Augmented_path( i );
}
}
return Ans;
}
复杂度分析：
| 时间 | 空间 | |
|---|---|---|
| 邻接矩阵 | ||
| 邻接表 |
3.例题
1. 洛谷 P1894 (完美的牛栏The Perfect Stall)
把奶牛看做x部，牛栏看做y部，将奶牛和它喜欢的牛栏连一条边，求该图的最大匹配即可。
代码如下：
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
int n,m,fx[ 205 ],fy[ 205 ];
bool vis[ 205 ];
vector< int > Graph[ 205 ];
bool Augmented_path( int u ) { //求增广路经
for( int i = 0 ; i < Graph[ u ].size( ) ; i ++ ) {
int v = Graph[ u ][ i ];
if( !vis[ v ] ) {
vis[ v ] = 1;
if( fy[ v ] == -1 || Augmented_path( fy[ v ] ) ) {
fx[ u ] = v , fy[ v ] = u;
return 1;
}
}
}
return 0;
}
int Hungary( ) { //匈牙利算法
int Ans = 0;
memset( fx , -1 , sizeof( fx ) );
memset( fy , -1 , sizeof( fy ) );
for( int i = 1 ; i <= n ; i ++ ) {
if( fx[ i ] == -1 ) {
memset( vis , 0 , sizeof( vis ) );
Ans += Augmented_path( i );
}
}
return Ans;
}
int main( ) {
int x,y;
scanf("%d %d",&n,&m);
for( int i = 1 ; i <= n ; i ++ ) {
scanf("%d",&x);
for( int j = 1 ; j <= x ; j ++ ) {
scanf("%d",&y);
Graph[ i ].push_back( y ); //将奶牛和它喜欢的牛栏连一条边
}
}
printf("%d",Hungary());
return 0;
}
2. ZOJ P1002 (Fire Net)
如果在一个点放了一个碉堡，那么他的行列在没有墙的情况下就不能再放另个一个碉堡，那么我们不如把它的行看做一个部分，他的列看做一部分。每个行部分与每个列部分之间最多只能放一个碉堡，所以在每个行部分与每个列部分之间连一条边，求图的最小点覆盖（即用最少的点覆盖整个图）。
下面引入一个定理：图的最小点覆盖=图的最大匹配
用匈牙利算法求解最大匹配即可，代码如下：
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;
int n,k,fx[ 405 ],fy[ 405 ];
bool vis[ 405 ],f[ 405 ][ 405 ];
vector< int > Graph[ 405 ];
bool Augmented_path( int u ) {
for( int i = 0 ; i < Graph[ u ].size( ) ; i ++ ) {
int v = Graph[ u ][ i ];
if( !vis[ v ] ) {
vis[ v ] = 1;
if( fy[ v ] == -1 || Augmented_path( fy[ v ] ) ) {
fx[ u ] = v , fy[ v ] = u;
return 1;
}
}
}
return 0;
}
int Hungary( ) {
int Ans = 0;
memset( fx , -1 , sizeof( fx ) );
memset( fy , -1 , sizeof( fy ) );
for( int i = 1 ; i <= k ; i ++ ) {
if( fx[ i ] == -1 ) {
memset( vis , 0 , sizeof( vis ) );
Ans += Augmented_path( i );
}
}
return Ans;
}
int a1[ 25 ][ 25 ],a2[ 25 ][ 25 ];
char s[ 25 ][ 25 ];
void Init( ) {
k = 1;
for( int i = 1 ; i <= n ; i ++ ) { //将行相连的置为一个部分
for( int j = 1 ; j <= n ; j ++ ) {
if( s[ i ][ j ] == 'X' ) {
if( s[ i ][ j - 1 ] == '.' )
k ++;
}
else
a1[ i ][ j ] = k;
}
k ++;
}
k = 1;
for( int i = 1 ; i <= n ; i ++ ) { //将列相连的置为一个部分
for( int j = 1 ; j <= n ; j ++ ) {
if( s[ j ][ i ] == 'X' ) {
if( s[ j - 1 ][ i ] == '.' )
k ++;
}
else
a2[ j ][ i ] = k;
}
k ++;
}
for( int i = 1 ; i <= n ; i ++ ) //将不同的行列部分之间连边
for( int j = 1 ; j <= n ; j ++ )
if( !f[ a1[ i ][ j ] ][ a2[ i ][ j ] ] && a1[ i ][ j ] && a2[ i ][ j ] ) {
f[ a1[ i ][ j ] ][ a2[ i ][ j ] ] = 1;
Graph[ a1[ i ][ j ] ].push_back( a2[ i ][ j ] );
}
}
int main( ) {
scanf("%d",&n);
for( int i = 1 ; i <= n ; i ++ )
for( int j = 1 ; j <= n ; j ++ )
cin >> s[ i ][ j ];
Init( );
printf("%d",Hungary());
return 0;
}